package com.huangpeng.algorithm.dataStructure;

import java.util.Arrays;

/**
 * @Author hp
 * @Title 计数排序
 * @Package
 * @Date 2022/1/17 17:18
 * @Description
 * @Version 1.0
 */
public class CountingSort {
    /**
     * 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
     * @param a
     * @param n
     */
    public void countingSort(int[] a,int n){
        if(n <= 1){
            return;
        }
        // 查找数组中数据的范围
        int max = a[0];
        for (int i = 1; i < n; i++) {
            if(max < a[i]){
                max = a[i];
            }
        }
        // 申请一个计数数组 c，下标大小 [0,max]
        int[] c = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            c[i] = 0;
        }
        // 计算每个元素的个数，放入 c 中
        for (int i = 0; i < n; i++) {
            c[a[i]]++;
        }
        // 依次累加
        for (int i = 1; i <= max; i++) {
            c[i] = c[i - 1] + c[i];
        }
        // 临时数组 r，存储排序之后的结果
        int[] r = new int[n];
        // 计算排序的关键步骤，有点难理解
        for (int i = n - 1; i >= 0 ; --i) {
            int index = c[a[i]] - 1;
            r[index] = a[i];
            c[a[i]]--;
        }
        // 将结果拷贝给 a 数组
        for (int i = 0; i < n; i++) {
            a[i] = r[i];
        }

        System.out.println("********** ==" + Arrays.toString(a));
    }

    public static void main(String[] args) {
        int[] a = {2,1,10,9,7,12};
        int n = 6;
        CountingSort countingSort = new CountingSort();
        countingSort.countingSort(a,n);
    }
}
